群论

一.群

1.群的定义

对于一个集合 $S$ 和定义在这个集合上的二元运算 $*$ , 满足：

• 封闭性。 $\forall a \in S,b \in S$ ，$a*b \in S$

• 结合律。 $a*b*c=a*(b*c)$

• 单位元。 $\exists \epsilon \in S$ , $a*\epsilon = \epsilon * a=a$

• 逆元。 $\forall a \in S$ , $\exists b \in S$ , $a * b = \epsilon$ , 记作 $a'$

那么称 $(S,*)$ 为一个群。

值得注意的是，一个群的单位元和逆元都是唯一的。

2.子群

若 $G(S,*)$ 为一个群，若 $T \subseteq S$ ，且 $H(T,*)$ 也为一个群，那么称 $H$ 为 $G$ 的子群，记作 $H \le G$

3.陪集

左陪集：若群 $H$ 为群 $G$ 的一个子群，且对于 $g \in G$，$gH=\{gh|h \in H \}$。

同样可以定义右陪集。

注意陪集可能不包含单位元，不一定是群。

陪集的性质：

1. $|H|=|gH|$
2. $g \in gH$
3. $gH=H \Leftrightarrow g \in H$
4. $aH=bH \Leftrightarrow a * b^{-1} \in H$
5. $aH \not= BH \Rightarrow aH \bigcap bH=\varnothing$
6. $\displaystyle \bigcup_{g \in G} gH={G}$

二.拉格朗日定理

$[G:H]$: $G$ 中 $H$ 不同陪集的数量

$G~/~H~$: $G$ 中所有 $H$ 的左陪集

有：

$|H|×[G:H]=|G|$

证明：由陪集的性质 1、5、6 显然。

三.置换群

1.置换

对于集合 $S=\{a_1,a_2 \dots a_n\}$ , 一个置换 $f$ 可表示为：

$f=\begin{pmatrix} a_1,a_2,\dots,a_n\\ a_{p_1},a_{p_2},\dots,a_{p_n} \end{pmatrix}$

$p$ 为 $1\sim n$ 的排列，意义为将 $a_i$ 映射为 $a_{p_i}$。

$f=\begin{pmatrix} a_{p_1},a_{p_2},\dots,a_{p_n}\\ a_{q_1},a_{q_2},\dots,a_{q_n} \end{pmatrix}, g=\begin{pmatrix} a_1,a_2,\dots,a_n\\ a_{p_1},a_{p_2},\dots,a_{p_n} \end{pmatrix}$

$f \times g=f(g(x))=\begin{pmatrix} a_1,a_2,\dots,a_n\\ a_{q_1},a_{q_2},\dots,a_{q_n} \end{pmatrix}$

称为置换的乘法。

2.循环置换

一种特殊的置换，其中：

$f=(a_1,a_2,\dots,a_n)=\begin{pmatrix} a_1,a_2,\dots,a_n\\ a_2,a_3,\dots,a_1 \end{pmatrix}$

任意一个置换都可以表示为若干不相交的循环置换的乘积，例如

$\begin{pmatrix}a_1,a_2,a_3,a_4,a_5\\ a_3,a_1,a_2,a_5,a_4\end{pmatrix}=(a_1,a_3,a_2) \times (a_4,a_5)$

将一个置换 $f$ 拆分的循环置换个数记为 $c(f)$

3.置换群

若 $S$ 包含所有的 $n!$ 个不同 $n$ 元置换，$G(S,\times)$ 为一个群，证明如下：

• 封闭性。 两个 $n$ 元置换的乘积仍为 $n$ 元置换，包含于 $S$。
• 结合律。置换的乘法有结合律。
• 单位元。置换 $\begin{pmatrix}a_1,a_2,\dots,a_n\\ a_1,a_2,\dots,a_n\end{pmatrix}$，也称恒等置换。
• 逆元。上下两行交换即可。

$G$ 的子群称作置换群。

四.Burnsied 引理 和 Pólya 定理

1.轨道稳定子定理

对于作用在集合 $X$ 上的群 $G$ 和集合 $X$ 的一个元素 $x$

$x$ 的轨道：$G(x)=\{ g(x) | g \in G\}$

$x$ 的稳定子：$G^x=\{ g \in G| g(x)=x\}$

这里 $g(x)$ 为群作用的函数，例如上文提到的置换。

1. $G^x$ 为 $G$ 的子群。

   证明：

   • 封闭性。 $f(x)=x,g(x)=x,f \times g=f(g(x))=x$,所以 $f \times g \in G^x$
   • 结合律。显然。
   • 单位元。$\epsilon(x)=x$，所以 $\epsilon \in G^x$
   • 逆元。$\forall g \in G$，因为 $g\times g'=\epsilon$ , $g(x)=\epsilon(x)=x$,所以 $g'(x)=x$，$g'(x) \in G$

2. $|G(x)|=[G:G^x]$

   证明：

   对于 $f(x)=g(x)$ , $f \times g^{-1}=\epsilon$

   若有两个 $f(x)=g(x),f \times g^{-1} = x = \epsilon(x)$ ，所以 $f \times g^{-1} \in G^x$ , $\Rightarrow fG^x = gG^x$ , 反之亦然。

   即不同的 $g$ 对应不同的陪集。

   所以对于 $G(x)$ 中的 $g$ , 构造对应陪集为 $gG^x$。

   感觉在伪证。

轨道稳定子定理：

$|G(x)| \times |G^x|= |G|$

证明：

因为 $G^x$ 为 $G$ 的子群，由拉格朗日定理得：

$|G^x| \times [G:G^x]=|G|$

由性质2得:

$|G^x| \times |G(x)| = |G|$

证毕。

2.Burnside 引理

若一个置换群 $G$ 作用于 $X$ , $X/G$ 表示在群 $G$ 作用下 $X$ 的所有等价类的集合。(注意每个等价类也是一个集合，若两个元素在 $G$ 作用下可以转化则属于同一个等价类)

$X^g$ 表示在 $g$ 的作用下不变的 $X$ 中元素的集合。

那么有：

$|X/G|=\frac{1}{|G|}\sum_{g \in G} |X^g|$

证明：

$\begin{aligned} \sum_{g\in G} |X^g|&=\sum_{x \in X} |G^x| \\ &=\sum_{x \in X} \frac{|G|}{|G(x)|} \\ &=|G|\sum_{x \in X} \frac{1}{|G(x)|} \\ &= |G|\sum_{Y \in X / G } \sum_{x \in Y} \frac{1}{|G(x)|} \\ &= |G|\sum_{Y \in X / G } \sum_{x \in Y} \frac{1}{|Y|} \\ &= |G|\sum_{Y \in X/G}1 \\ &= |G||X/G| \end{aligned}$

即：

$|X/G|=\frac{1}{|G|}\sum_{g \in G} |X^g|$

可以参考 oi-wiki 的例子。

3.Pólya 定理

$|X/G|=\frac{1}{|G|}\sum_{g \in G} m^{c(g)}$

证明：

由 burnside 引理发现，在 $g$ 作用下的不动点的充要条件是每一个循环置换里元素同色。

那么式子就很显然了。

五.例题

1.P4980 【模板】Pólya 定理

首先置换群 $G$ 包含的元素分别为: 旋转 $1$ 个点,旋转 $2$ 个点...旋转 $n$ 个点

不难发现，旋转 $k$ 个点的 $c(g)=\gcd(n,k)$，原因如下：

所有循环置换所包含的元素个数相同，均为 $\frac{\text{lcm(n,k)}}{k}$。(旋转次数/旋转步长)

那么循环置换的个数便为 $\frac{n}{\frac{\text{lcm}(n,k)}{k}}=\gcd(n,k)$

由 polya 定理得：

$|X/G|=\frac{1}{n}\sum_{i=1}^n n^{\gcd(i,n)}$

化简可得：

$|X/G|=\frac{1}{n}\sum_{d|n}n^d\varphi(\frac{n}{d})$

直接计算即可，复杂度 $\mathcal{O(n^{\frac{3}{4}})}$

#include <cstdio>

const int Mod = 1e9 + 7;
int Add( int x , int y ) { x += y; return x >= Mod ? x - Mod : x; }
int Sub( int x , int y ) { x -= y; return x < 0 ? x + Mod : x; }
int Mul( int x , int y ) { return 1ll * x * y % Mod; }
int Quick_pow( int x , int po ) { int Ans = 1; for( ; po ; po >>= 1 , x = Mul( x , x ) ) if( po & 1 ) Ans = Mul( Ans , x ); return Ans; }
int Inv( int x ) { return Quick_pow( x , Mod - 2 ); }
int Div( int x , int y ) { return 1ll * x * Inv( y ) % Mod; }


int phi( int n ) {
    int Ans = n;
    for( int i = 2 ; i * i <= n ; i ++ )
        if( n % i == 0 ) {
            Ans = Ans / i * ( i - 1 );
            while( n % i == 0 ) n /= i;
        }
    if( n > 1 ) Ans = Ans / n * ( n - 1 );
    return Ans;
}

int T , n;
int main( ) {
    scanf("%d",&T);
    while( T -- ) {
        scanf("%d",&n);
        int Ans = 0;
        for( int i = 1 ; i * i <= n ; i ++ )
            if( n % i == 0 ) {
                Ans = Add( Ans , Mul( Quick_pow( n , i ) , phi( n / i ) ) );
                if( i * i != n )
                    Ans = Add( Ans , Mul( Quick_pow( n , n / i ) , phi( i ) ) );
            }
        printf("%d\n", Div( Ans , n ) );
    }
    
    return 0;
}